package io.github.hadyang.leetcode.bytedance;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;

import io.github.hadyang.leetcode.TreeNode;

/**
 * 二叉树的锯齿形层次遍历
 *
 * <p>给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
 */
public class Link1027 {

  @Test
  public void test() {
    TreeNode treeNode1 = new TreeNode(3);
    TreeNode treeNode2 = new TreeNode(9);
    TreeNode treeNode3 = new TreeNode(20);
    TreeNode treeNode4 = new TreeNode(15);
    TreeNode treeNode5 = new TreeNode(7);

    treeNode1.left = treeNode2;
    treeNode1.right = treeNode3;
    treeNode3.left = treeNode4;
    treeNode3.right = treeNode5;

    System.out.println(zigzagLevelOrder(treeNode1));
  }

  public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
    List<List<Integer>> temp = new ArrayList<>();

    List<List<Integer>> res = new ArrayList<>();
    for (int i = 0; i < temp.size(); i++) {
      if (i % 2 == 1) {
        res.add(temp.get(i));
      } else {
        Collections.reverse(temp.get(i));
        res.add(temp.get(i));
      }
    }
    return res;
  }

  private void all(List<List<Integer>> res, TreeNode root, int level) {
    if (root == null) {
      return;
    }

    for (int i = 0; i < level - res.size() + 1; i++) {
      res.add(new LinkedList<>());
    }

    res.get(level).add(root.val);

    all(res, root.right, level + 1);
    all(res, root.left, level + 1);
  }
}
